home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Chip 1996 April
/
CHIP 1996 aprilis (CD06).zip
/
CHIP_CD06.ISO
/
hypertxt.arj
/
9501
/
E_HAZAS.CD
< prev
next >
Wrap
Text File
|
1995-10-27
|
7KB
|
111 lines
@VRejtvénymegfejtés@N
@VPárkeresés magyar módra@N
Senki ne gondoljon itt semmiféle rosszra, magazinunk
mûfajától idegen dologra, csupán (sajnos?) augusztusi
feladványunk megoldásáról lesz szó a továbbiakban.
Bonifert Csaba javasolta a következô feladat kitûzését:
egy társkeresô irodában minden fiúról és lányról
nyilvántartják, hogy kölcsönösen szimpatizálnak-e egymással.
Feladat a fiúkat és lányokat úgy párosítani, hogy a lehetô
legkevesebben maradjanak pár nélkül (csak fiú-lány
kapcsolatok lehetségesek, s azok is monogám jellegûek
legyenek!).
ùgy tûnik, kezd kiegyenlítôdni a nem hivatalos nyelvi
versengés eredménye: négy megfejtônk közül ketten C, ketten
Pascal nyelvû programot küldtek, a mégis megmaradó enyhe
Pascal fölényt (3:2) Déri Attila kétféle megoldása
biztosítja.
Ismét (sokadszor) gráfelméleti probléma szerepel
rovatunkban, talán nem véletlenül. A gráfok rendkívül sok --
egymástól igen eltérô módon megfogalmazható -- probléma
leírására alkalmazhatók, közlekedési, szállítási kérdésektôl
kezdve áramkörtervezési feladatokon keresztül sportversenyek
lebonyolításának megszervezéséig, vagy -- mint látható -- a
házasságközvetítésig.
Hogyan tudnánk tehát a kitûzött problémát pontosabban --
némi gráfelméleti terminus technicust használva -- leírni?
ùgynevezett páros gráffal van dolgunk, mert pontjai két
olyan csoportra oszthatók (tudniillik fiúkra és lányokra),
melyeken belül nincs él (kapcsolat), tehát él csak különbözô
halmazba tartozó pontokat köthet össze. Ráadásul mi
független éleket -- azaz olyanokat, melyeknek nincsen közös
pontjuk -- keresünk, ezzel zárva ki a többnejû(férjû)séget.
Ennek alapján a feladat egy páros gráf maximális független
élhalmazának megkeresését jelenti, tehát a párosítási
probléma egy speciális esetével van dolgunk.
Két út áll elôttünk: megpróbálhatjuk gráfunkat teljesen
általánosan, szisztematikusan feldolgozni, azaz elôállítjuk
az adott pontok és élek alapján az összes lehetséges
kombinációt, s kiválasztjuk a maximális élszámút. Sejthetô,
hogy a méretek növekedtével ez a metódus igencsak lelassul,
hiszen drámai mennyiségû lesz a lehetséges kombinációk
száma. Kellene tehát egy hatékonyabb eljárás. Ez lesz az
úgynevezett ""magyar módszer", amely Kônig Dénes és Egerváry
Jenô nevéhez fûzôdik (a század elsô felébôl), s amelynek
leírása megtalálható például Andrásfai Béla Ismerkedés a
gráfelmélettel, vagy Lovász-Gács szerzôpáros Algoritmusok c.
könyveiben. Ezt a módszert (is) ""programozta be" Déri
Attila, és Tóth Zoltán.
Mi is tehát ez a magyar módszer (másképpen az alternáló
utak módszere)? Képzeljük el (páros) gráfunkat úgy, hogy a
két halmaz pontjait (a fiúkat, illetve a lányokat) alul,
illetve fölül egy egyenes mentén rajzoljuk fel, a szimpátia
kapcsolatokkal egyetemben. Kezdjünk kiválasztani független
éleket (mondjuk vastagítsuk meg a választott vonalat).
Elôbb-utóbb megakadunk, pedig még maradt pártában leányzó
vagy legény. S most jön az algoritmus lényege: olyan utakat
(összefüggô élsorozatokat) fogunk keresni, amelyek fel nem
használt alsó pontokon indulnak, minden második élük már
vastag, és felsô, fel nem használt ponton végzôdnek. Egy
ilyen út ""vastag" éleit az út többi élére kicserélve
(azokat megvastagítva), a független élek számát növeljük.
(Érdemes egy kis ábrát rajzolva kipróbálni az eljárást.)
Most már csak az a kérdés, hogyan tudjuk ""lefordítani"
ezt (Tóth Zoltán kifejezését kölcsönvéve) a ""szeret-nem
szeret" mátrix feldolgozására, hiszen ez, a csupa nullát és
egyest tartalmazó tömb (""hivatalosan" adjacencia-mátrix
vagy szomszédossági mátrix) adja a kapcsolatok és így a gráf
legkézenfekvôbb gépi ábrázolását (olvasóink is ezt az
ábrázolásmódot választották). Világos, hogy az éleknek a
tömbbéli egyesek felelnek meg, így a fenti vonalvastagítás
valamely 1-es megjelölését (pl. értéke megnövelését 2-re)
jelenti. Jelöljük (jegyezzük) meg az összes olyan oszlopot,
amelybôl nem választottunk 1-est, majd a sorokra térünk át:
azokat jelöljük meg, amelyek a jelölt oszlopokat 1-esben
metszik, végül visszatérve az oszlopokra megjelöljük azokat,
amelyek a jelölt sorok valamelyikét 2-esben metszi. Ha már
nem tudunk ezen szabályok szerint jelölni (mondjuk áthúzni),
akkor vizsgáljuk meg azon megjelölt sorokat, amelyek
legfeljebb 1-est tartalmaznak. Megkeressük azt az 1-est, ami
miatt ezt a sort áthúztuk, ennek oszlopában azt a 2-est, ami
az oszlop kihúzásának volt az oka... és így tovább. Eljutunk
egy olyan 1-eshez, amelynek oszlopában nincs 2-es: és ekkor
ennek az útnak az 1-eseit 2-re, 2-seit 1-re változtatva a
kettesek számát növeltük. (Ezt a gondolatmenetet is
valószínûleg könnyebb papíron, ceruzával, egy barátságos
tömb mellett követni).
A fenti algoritmus rejtett módon két fontos gráfelméleti
tételt is tartalmaz. König Dénes tétele kimondja, hogy
bármely páros gráf független éleinek maximális száma egyenlô
az éleket leszúró pontok minimális számával -- ez egy újabb
megoldási lehetôséget is jelenthet a feladatra. Hall tétele
a probléma teljes megoldhatóságára ad feltételt: egy páros
gráfban akkor és csak akkor lehet minden ""alsó" ponthoz egy
vele összekötött ""felsô" pontot rendelni (különbözôhöz
különbözôt, azaz független élt), ha bármely @KN@N-re bármely @KN@N
darab alsó pont összesen legalább @KN@N felsô ponttal van
összekötve. Ez utóbbi tétel egy játékosabb (és könnyebb)
változata: egy táncmulatságon @KK@N férfi és @KK@N nô van jelen.
Mindenki ismeri az ellenkezô nemûeknek legalább a felét.
Bizonyítsuk be, hogy valamennyien táncra perdülhetnek úgy,
hogy ismerôssel ""lejtenek".
A havi nyertes -- sorsolás eredményeképpen -- Verbôczi
Zoltán lett, nyereménye 10 darab floppy. A CT BBS-en Tóth
Zoltán gyöngyösi megfejtônk számos extrával ellátott C
nyelvû programját, illetve az ötletgazda, Bonifert Csaba
(szintén C) megoldását találják meg olvasóink.
@KBánhegyesi Zoltán@N